﻿/*THÔNG TIN*********************************************************************
 *Tập tin		: Graph_Library.h
 *Mô tả			: Thư viện các định nghĩa các thuộc tính và phương thức về đồ thị
 *Ngày tạo		: 29/08/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

// Số ký tự nhiều nhất có thể đọc trên 1 dòng khi đọc tập tin .grf
#define MAX_CHAR 500

/*Lớp đồ thị*/
class GRAPH	{
private:
	// Cấu trúc lưu tọa độ đỉnh
	struct COORD	{
		double x, y;
	};

	// Số đỉnh, đỉnh xuất phát, đỉnh kết thúc
	uint16_t vertices, source, target;
	// Số cạnh
	uint32_t edges;
	// Ma trận kề lưu độ dài cạnh
	vector < vector <double> > length;

public:
	// Cấu trúc lưu cạnh
	struct EDGE	{
		uint16_t source, target;
	};

	// Thời gian bắt đầu và kết thúc thực hiện thuật toán
	clock_t start_time, finish_time;
	// Mảng lưu kết quả
	vector <uint16_t> result;
	// Mảng đánh dấu đỉnh đã được xét
	vector <bool> final;
	// Mảng lưu các đỉnh lân cận của i là neighbors[i]
	vector <vector <uint16_t> > neighbors;	

	// Phương thức khởi tạo
	GRAPH();

	// Lấy số đỉnh
	inline uint16_t Get_vertices();
	// Đặt số đỉnh
	inline void Set_vertices(uint16_t value);
	// Lấy số cạnh
	inline uint32_t Get_edges();
	// Đặt số cạnh
	inline void Set_edges(uint32_t value);
	// Lấy đỉnh xuất phát
	inline uint16_t Get_source();
	// Đặt đỉnh xuất phát
	inline void Set_source(uint16_t value);
	// Lấy đỉnh kết thúc
	inline uint16_t Get_target();
	// Đặt đỉnh kết thúc
	inline void Set_target(uint16_t value);
	// Lấy độ dài cạnh (i, j)
	inline double Get_length(uint16_t i, uint16_t j);
	// Đặt độ dài cạnh (i, j)
	inline void Set_length(uint16_t i, uint16_t j, double value);

	// In thông báo thời gian chạy thuật toán
	void Print_runtime();

	// Khởi tạo thông tin cơ bản về đồ thị
	fstream Initiate_graph(string input_file, bool type);

	// Đọc dữ liệu đồ thị từ file txt lưu danh sách cạnh
	bool Read_txt(bool mode, string input_file);

	// Nhận diện từng đỉnh đọc vào xâu
	char* Identify_vertex(char *edge_list_string, uint16_t &i);
	// Đọc danh sách đỉnh mà từ index có đường đi đến
	void GRAPH :: Read_all_vertices(fstream &f, uint16_t index, vector <EDGE> &edge_list);
	// Trả về khoảng cách theo công thức tọa độ giữa hai cạnh
	double Distance(COORD c1, COORD c2);
	// Lưu độ dài cạnh vào mảng length
	void Calc_length(vector <COORD> list, vector <EDGE> edge_list);
	// Đọc dữ liệu đồ thị GRAFITI từ file .grf
	bool Read_grf(string input_file);

	// Đọc dữ liệu đồ thị từ file .txt hoặc .grf
	bool Read_graph(string input_file, bool type, bool mode);
	//Lấy đỉnh xuất phát và đỉnh kết thúc ngẫu nhiên
	void Random_source_and_target();
	// Thiết lập cho mảng neighbors
	void Build_neighbors();

	// Mở file .dot mới, opt là tùy chọn phụ thuộc thuật toán
	fstream New_output_file(string input_header, string opt, string extension);
	// Lưu đồ thị dưới dạng file .dot
	void Print_graph_to_dot(string input_file);
	// Dịch từ file .dot sang hình ảnh .bmp, opt là tùy chọn phụ thuộc thuật toán
	void Dot_to_bmp(string input_file, string opt);
};/*Kết thúc khai báo lớp GRAPH*/

/*Phương thức khởi tạo*/
GRAPH :: GRAPH()	{
	vertices = 0;
	edges = 0;
	source = 0;
	target = 0;
	length.clear();
	start_time = 0;
	finish_time = 0;
	result.clear();
	final.clear();
	neighbors.clear();
}/*Kết thúc phương thức GRAPH*/

/*Lấy số đỉnh*/
uint16_t GRAPH :: Get_vertices()	{
	return vertices;
}/*Kết thúc phương thức Get_vertices*/

/*Đặt số đỉnh*/
void GRAPH :: Set_vertices(uint16_t value)	{
	vertices = value;
}/*Kết thúc phương thức Set_vertices*/

/*Lấy số cạnh*/
uint32_t GRAPH :: Get_edges()	{
	return edges;
}/*Kết thúc phương thức Get_edges*/

/*Đặt số cạnh*/
void GRAPH :: Set_edges(uint32_t value)	{
	edges = value;
}/*Kết thúc phương thức Set_edges*/

/*Lấy đỉnh xuất phát*/
uint16_t GRAPH :: Get_source()	{
	return source;
}/*Kết thúc phương thức Get_source*/

/*Đặt đỉnh xuất phát*/
void GRAPH :: Set_source(uint16_t value)	{
	source = value;
}/*Kết thúc phương thức Set_source*/

/*Lấy đỉnh đích*/
uint16_t GRAPH :: Get_target()	{
	return target;
}/*Kết thúc phương thức Get_target*/

/*Đặt đỉnh đích*/
void GRAPH :: Set_target(uint16_t value)	{
	target = value;
}/*Kết thúc phương thức Set_target*/

/*Lấy độ dài cạnh*/
double GRAPH :: Get_length(uint16_t i, uint16_t j)	{
	return length[i][j];
}/*Kết thúc phương thức Get_length*/

/*Đặt độ dài cạnh*/
void GRAPH :: Set_length(uint16_t i, uint16_t j, double value)	{
	length[i][j] = value;
}/*Kết thúc phương thức Set_length*/

/*In thông báo thời gian chạy thuật toán*/
void GRAPH :: Print_runtime()	{
	finish_time = clock();
	cout << "Xong trong " 
		 << double(finish_time - start_time) / CLOCKS_PER_SEC << " s.\n";
}/*Kết thúc phương thức Print_runtime*/

/*Khởi tạo thông tin cơ bản về đồ thị
type = true: đọc từ file .txt
type = false: đọc từ file .grf*/
fstream GRAPH :: Initiate_graph(string input_file, bool type)	{
	fstream f(input_file, ios :: in);
	if (!f)	{
		cout << "Loi: File khong ton tai\n";
		return f;
	}
	cout << "Doc du lieu do thi..........";

	// Đọc số đỉnh và số cạnh
	if (type)	{
		f >> vertices >> edges;
	}
	else	{
		char *line = new char[MAX_CHAR];

		while (!f.eof())	{
			f.getline(line, MAX_CHAR);
		
			if (line[1] == '\0')
				break;
			else
				++vertices;
		}

		--vertices;
	}
	
	// Khởi tạo mảng length
	length.resize(vertices);

	for (uint16_t i=0; i!=vertices; ++i)	{
		length[i].resize(vertices);
		fill(length[i].begin(), length[i].end(), UINT16_MAX);
	}

	if (type)
		return f;
	else
		return fstream(input_file, ios :: in);
}/*Kết thúc phương thức Initiate_graph*/

/*Đọc dữ liệu đồ thị từ file txt lưu danh sách cạnh với 2 chế độ:
mode = true: Đọc đồ thị có trọng số
mode = false: Đọc đồ thị không trọng số*/
bool GRAPH :: Read_txt(bool mode, string input_file)	{
	fstream f = Initiate_graph(input_file, true);
	if (!f)
		return false;

	// Đọc dữ liệu danh sách cạnh
	uint16_t temp_1, temp_2, i;
	
	if (!mode)	{
		for (i=0; i!=edges; ++i)	{
			f >> temp_1 >> temp_2;
			length[temp_1-1][temp_2-1] = 1.0;
		}
	}
	else	{
		double temp_3;

		for (i=0; i!=edges; ++i)	{
			f >> temp_1 >> temp_2 >> temp_3;
	
			if (temp_3 > 0.0)
				length[temp_1-1][temp_2-1] = temp_3;
		}
	}

	f.close();
	cout << "Xong.\n";
	return true;
}/*Kết thúc phương thức Read_txt*/

/*Nhận diện từng đỉnh đọc vào xâu */
char* GRAPH :: Identify_vertex(char *edge_list_string, uint16_t &i)	{
	uint16_t count = 0;
	char *num = new char[10];

	num[0] = edge_list_string[i];
				
	while ( edge_list_string[i+1]>='0' && edge_list_string[i+1]<='9' )	{
		++count;
		++i;
		num[count] = edge_list_string[i];
	}
	
	num[count+1] = '\0';

	return num;
}/*Kết thúc phương thức Identify_vertex*/

/*Đọc danh sách đỉnh mà từ index có đường đi đến*/
void GRAPH :: Read_all_vertices(fstream &f, uint16_t index, vector <EDGE> &edge_list)	{
	char *edge_list_string = new char[MAX_CHAR];

	f.getline(edge_list_string, MAX_CHAR);

	size_t len = strlen(edge_list_string);

	if (len)	{
		// Trích xuất các đỉnh
		uint16_t i=0;
	
		while (i != len)	{
			if (edge_list_string[i]>='0' && edge_list_string[i]<='9' )	{
				char *num = Identify_vertex(edge_list_string, i);
			
				// Lưu danh sách cạnh vào mảng edge_list
				EDGE e;
				e.source = index - 1;
				e.target = uint16_t(atol(num)) - 1;
				edge_list.push_back(e);

				++edges;
			}			

			++i;
		}
	}
}/*Kết thúc phương thức Read_all_vertices*/

/*Tính khoảng cách theo công thức tọa độ giữa hai cạnh*/
double GRAPH :: Distance(COORD c1, COORD c2)	{
	double dx = c1.x - c2.x, dy = c1.y - c2.y;

	return sqrt(dx*dx + dy*dy);
}/*Kết thúc phương thức Distance*/

/*Lưu độ dài cạnh vào mảng length*/
void GRAPH :: Calc_length(vector <COORD> list, vector <EDGE> edge_list)	{
	uint16_t u, v;

	for (uint16_t i=0; i!=edges; ++i)	{
		u = edge_list[i].source;
		v = edge_list[i].target;

		length[u][v] = Distance(list[u], list[v]);
	}
}/*Kết thúc phương thức Calc_length*/

/*Đọc dữ liệu đồ thị GRAFITI từ file .grf*/
bool GRAPH :: Read_grf(string input_file)	{
	fstream f = Initiate_graph(input_file, false);
	if (!f)
		return false;

	// Danh sách tọa độ các đỉnh
	vector <COORD> list(vertices);
	// Danh sách các cạnh
	vector <EDGE> edge_list;
	edge_list.clear();

	while (!f.eof())	{
		// Đọc tên đỉnh
		uint16_t index = 0;

		f >> index;

		if (index == 0)
			break;

		// Đọc tọa độ đỉnh
		f >> list[index-1].x >> list[index-1].y;
		
		Read_all_vertices(f, index, edge_list);
	}
	
	Calc_length(list, edge_list);
	
	cout << "Xong.\n";
	return true;
	f.close();
}/*Kết thúc phương thức Read_grf*/

/*Đọc dữ liệu đồ thị từ file .txt hoặc .grf
type = true: đọc từ file .txt
+	mode = true: đọc đồ thị có trọng số
+	mode = false: đọc đồ thị không trọng số
type = false: đọc từ file .grf*/
bool GRAPH :: Read_graph(string input_file, bool type, bool mode)	{
	if (type)	{
		if (!Read_txt(mode, input_file))
			return false;
	}
	else	{
		if (!Read_grf(input_file))
			return false;
	}

	return true;
}/*Kết thúc phương thức Read_graph*/

/*Thiết lập cho mảng neighbors*/
void GRAPH :: Build_neighbors()	{
	for (uint16_t i=0; i<Get_vertices(); i++)	{
		vector <uint16_t> neighbor;

		for (uint16_t j=0; j<Get_vertices(); j++)
			if (Get_length(i, j)!=UINT16_MAX)
				neighbor.push_back(j);
		
		neighbors.push_back(neighbor);
	}
}/*Kết thúc hàm Build_neighbors*/

/*Lấy đỉnh xuất phát và đỉnh kết thúc ngẫu nhiên*/
void GRAPH :: Random_source_and_target()	{
	srand(uint16_t(time(0)));

	if (vertices > 1)	{
		source = uint16_t( rand() ) % Get_vertices();

		do	{
			target =  uint16_t( rand() ) % Get_vertices();
		}	while (target == source);
	}

	cout << "Dinh xuat phat: " << source + 1 << "\n";
	cout << "Dinh ket thuc: " << target + 1 << "\n";
}/*Kết thúc phương thức Random_source_and_target*/

/*Mở file .dot mới, opt là tùy chọn phụ thuộc thuật toán*/
fstream GRAPH :: New_output_file(string input_header, string opt, string extension)	{
	cout << "Luu ket qua ra file " << input_header << opt << extension << "..........";

	return fstream(input_header + opt + extension, ios :: out);
}/*Kết thúc phương thức New_dot_file*/

/*Lưu đồ thị dưới dạng file .dot*/
void GRAPH :: Print_graph_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "", ".dot");

	f << "digraph " << input_header << " {\n";

	for (uint16_t i=0; i<vertices; ++i)
		for (uint16_t j=0; j<vertices; ++j)	{
			if (length[i][j] != UINT16_MAX)
				f << i+1 << " -> " << j+1 << " [label = \"" << length[i][j] << "\"]\n";
		}

	f << "label = \"\\n\\nDo thi voi du lieu tu file " << input_file << "\"\n}";
	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_graph_to_dot*/

/*Dịch từ file .dot sang hình ảnh .bmp, opt là tùy chọn phụ thuộc thuật toán*/
void GRAPH :: Dot_to_bmp(string input_file, string opt)	{
	string input_header(input_file.begin(), input_file.end()-4);

	cout << "Luu ket qua ra file " << input_header << opt << ".bmp" << "..........";

	string command = "dot -Tbmp -o" + input_header + opt + ".bmp " + input_header + opt + ".dot";

	system(command.c_str());

	cout << "Xong.\n\n\n";

	string out_name = input_header + opt + ".bmp ";
	system(out_name.c_str());
}/*Kết thúc phương thức Dot_to_bmp*/
